/*
 * sort.c
 *
 *  Created on: 2010-8-19
 *      Author: Anders
 */

#include <stdio.h>

#define MAX_ARRAY_SIZE 100
#define DEBUG_PRINT

#ifdef DEBUG_PRINT
#define PRINT  printf
#else
#define PRINT(...) do {} while (0)
#endif

void usage()
{
	printf("[Usage] select <index>\n");
}

int partition(int array[], int p, int r)
{
	int i, j, key, temp;

	i = p - 1;
	key = array[i];

	PRINT("[partition] %d, %d\n", p, r);

	for (j = p; j < r; j++) {
		if ( array[j] < key) {
			if(++i == j) {
				continue;
			}
			temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}

	array[p - 1] = array[i];	
	array[i] = key;

	PRINT("pivot: %d\n", i + 1);

	return (i + 1);
}

int random_select(int array[], int q, int r, int i)
{
	int p, k;

	p = partition(array, q, r);
	k = p - q + 1;
	if (i == k)
		return p;
	if (i < k)
		return random_select(array, q, p - 1, i);
	else
		return random_select(array, p + 1, r, i - k);
}

int
main(int argc, char **argv)
{
	int array[MAX_ARRAY_SIZE] = {20, 4, 23, 3, 1, 2, 5, 19, 18, 10, 
	                             16, 17, 15, 7, 9, 8, 22, 21, 6, 11, 
	                             12, 13, 14};
	int i, n;
	int  index, ret;

	n = 23;

	if (argc != 2) {
		usage();
		return;
	}
	if ((index = atoi(argv[1])) > n || index < 0) {
		printf("invalid index\n");
		return;
	}
	
	// print array 
	printf("Array: ");
	for (i = 0; i < n; i++) {
		printf("%d, ", array[i]);
	}
	PRINT("\n");
	
	ret = random_select(array, 1, n, index);
	printf("the %dth value of array is array[%d]: <%d>\n", index, ret, array[ret - 1]);
}

